package _11_整理题目._2_二叉树_递归_dfs_bfs._递归._生成二叉树;

import org.junit.Test;
import util.TreeNode;

public class _04_将升序数组转化为平衡二叉搜索树 {
    
    public TreeNode sortedArrayToBST (int[] num) {
        if (num == null) return null;
        return recursion(num, 0, num.length-1);
    }
    
    private TreeNode recursion(int[] num, int left, int right) {
        if (left > right) return null;
        int mid = left + (right-left+1) / 2;
        TreeNode leftTree = recursion(num, left, mid-1);
        TreeNode rightTree = recursion(num, mid+1, right);
        
        TreeNode root = new TreeNode(num[mid]);
        if (leftTree != null) root.left = leftTree;
        if (rightTree != null) root.right = rightTree;
        
        return root;
    }
    
    @Test
    public void main() {
        int[] num = {-1, 0, 1, 2};
        TreeNode root = sortedArrayToBST(num);
        TreeNode.printTree(root);
    }
    
}
